package ue.a4;

public class Gray {
	
	static boolean	Debug	= true;
	
	public static void outbin(String s, int n, String ln) {
		
		System.out.print(s + " " + n + ": " + tobin(n) + ln);
		
	}
	
	public static String tobin(int n) {
		String result = "";
		while (n > 0) {
			result = (n % 2) + result;
			n = n / 2;
		}
		return result;
	}
	
	public static int toGray(int n) {
		int result = 0;
		if (Debug) {
			outbin("n", n, " ");
		}
		result = (n >> 1); // bitshift right
		if (Debug) {
			outbin("(shifted", result, ")");
		}
		result = result ^ n; // xor
		if (Debug) {
			outbin("(xor", result, ")\n");
		}
		return result;
		
	}
	
	// http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code
	
	public static int fromGray(int g) {
		int maske = 0;
		maske = (g >> 1);
		if (Debug) {
			outbin("(maske", maske, ") ");
			outbin("(g", g, ")\n");
			
		}
		while (maske != 0) {
			g = g ^ maske;
			maske = maske >> 1;
			if (Debug) {
				outbin("(maske", maske, ") ");
				outbin("(g", g, ")\n");
				
			}
		}
		
		return g;
	}
	
	public static void main(String[] args) {
		int c = 0;
		// int dummy = 0;
		c = Integer.parseInt(args[0]);
		// for (int i = 0; i < c; i++) {
		// dummy = fromGray(toGray(i));
		// }
		graytable("", c);
		
	}
	
	// source
	// http://introcs.cs.princeton.edu/java/23recursion/GrayCode.java.html
	// append reverse of order n gray code to prefix string, and print
	public static void yargtable(String prefix, int bits) {
		if (bits == 0) {
			
			System.out.println(prefix);
			
		} else {
			graytable(prefix + "1", bits - 1);
			yargtable(prefix + "0", bits - 1);
		}
	}
	
	// append order n gray code to end of prefix string, and print
	public static void graytable(String prefix, int bits) {
		if (bits == 0) {
			System.out.println(prefix);
		} else {
			graytable(prefix + "0", bits - 1);
			yargtable(prefix + "1", bits - 1);
		}
	}
	
}
